Cartograms are a well-known technique for showing geography-related statistical information, such as population demographics, election results and epidemiological data. The basic idea is to distort a map by resizing its regions according to some geographically related statistical parameter, but in a way that keeps the map recognizable. Cartographers and geographers have used cartograms since long before computers were available to make displays. Because cartograms are difficult to make by hand, the study of programs to draw them is of interest.
Other visualization techniques include the conventional choropleth map. A choropleth map is a map divided into regions that are shaded according to the value of a variable for that region. High values are often concentrated in highly populated areas, and low values may be spread out across sparsely populated areas. Such maps therefore tend to highlight patterns in less dense areas where few people live. In contrast, cartograms display areas in relation to an additional parameter, such as population. Patterns may then be displayed in proportion to that parameter (e.g. the number of people involved) instead of the raw size of the area involved. A population-based cartogram is presented in FIG. 1B. The cartogram gives a much different impression of overall trends, as compared with the original map (FIG. 1A).
For a cartogram to be recognizable it is important to preserve the global shape or outline of the input map, a requirement that has been overlooked in the past. To address this, the inventors' objective function for cartogram drawing includes both global and local shape preservation. To measure the degree of shape preservation, a shape similarity function is proposed. The function is based on a Fourier transformation of the polygons' curvatures. Also, because the application goal is visualization of dynamic network behavior, an algorithm is needed that recalculates a cartogram in a few seconds. No previous algorithm known to the inventors provides adequate performance with an acceptable level of quality for that application.
In the present application, the inventors formally define a family of cartogram drawing problems, and show that even simple variants are unsolvable in the general case. The feasible variants are NP-complete; i.e., the problem is both NP (verifiable in nondeterministic polynomial time) and NP hard (any other NP problem can be translated into this problem). Heuristics are therefore needed to solve the problem. Previously proposed solutions suffer from problems with the quality of the generated drawings.
The present application describes an efficient iterative scanline algorithm to reposition edges while preserving local and global shapes. Scanlines may be generated automatically, or entered interactively to guide the optimization process more closely. The algorithm is applied to a number of example data sets, providing a detailed comparison of the two variants of our algorithm and previous approaches.
A cartogram can be seen as a generalization of an ordinary map. In that interpretation, an arbitrary parameter vector gives the intended sizes of the cartogram's regions, so an ordinary map is simply a cartogram with sizes proportional to land area. In addition to the classical applications mentioned above, a key motivation for cartograms as a general information visualization technique is to have a method for trading off shape and area adjustments.
For a cartogram to be effective, a human must be able to quickly understand the displayed data and relate it to the original geographical model. Recognition, in turn, depends on preserving basic properties, such as shape, orientation, and contiguity. That, however, is difficult to achieve in the general case because it is impossible to retain even the original map's topology. Because the generation of contiguous cartograms by simultaneous optimization of those objectives is difficult, most currently available algorithms are very time-consuming.
Cartograms may be made by contiguous or non-contiguous distortions. The non-contiguous case is much simpler because the input map topology does not have to be preserved. As seen in FIGS. 2A-2H, hand-made non-contiguous cartograms have been made with overlapping or touching circles (FIG. 2D), by eliminating some of the original map's adjacencies (FIG. 2C), or even by drawing disconnected shapes over the original regions (FIG. 2B).
Previous attempts to automate the drawing of contiguous cartograms do not yield results comparable to good hand-made drawings. One reason is that straight lines, right angles and other features considered important in human recognition of cartograms are obliterated. Methods that are radial in nature such as the conformal maps proposed by W. R. Tobler, “Cartograms and Cartosplines,” Proceedings of the 1976 Workshop on Automated Cartography and Epidemiology, 53-58 (1976) (FIG. 2A), the radial expansion method of S. Selvin, D. Merrill, J. Schulman, S. Sacks, L. Bedell, and L. Wong, “Transformations of Maps to Investigate Clusters of Disease,” Social Science and Medicine, V. 26, no. 2, at 215-221 (1988) (FIG. 2F) and the line integral method of Sabir Gusein-Zade and Vladimir Tikunov, “A New Technique for Constructing Continuous Cartograms,” Cartography and Geographic Information Systems, V. 20, no. 3 at 66-85 (1993) (FIG. 2G) do not provide acceptable results, since the shapes of the polygons are heavily deformed. Likewise, the pseudo-cartograms described by W. R. Tobler, “Pseudo-Cartograms,” The American Cartographer, V. 13, no. 1 at 43-40 (1986) (FIG. 2E) expand the lines of longitude and latitude to achieve a least root mean square area error. Very similar drawings have been made by approaching the problem as distortion viewing by nonlinear magnification. Radial forces are applied by Charles B. Jackel, “Using Arcview to Create Contiguous and Noncontiguous Area Cartograms,” Cartography and Geographic Information Systems, V. 24, no. 2 at 101-109 (1997) to change the size of polygons, moving the sides of each polygon relative to its centroid. That solver, however, runs slowly (e.g., taking 90 minutes to perform 8 iterations on a map of 6 New England states of the U.S.) and seems to have problems with non-convex input polygons and with self-intersections in the output.
Another family of approaches operates on a grid or mesh imposed on the input map. The “piezopleth” method of C. Cauvin, C. Schneider, and G. Cherrier, “Cartographic Transformations and the Piezopleth Method,” The Cartographic Journal, V. 26, no. 2 at 96-104 (December 1989) transforms the grid by a physical pressure load model. The cellular automaton approach of Daniel Dorling, Area Cartograms: Their Use and Creation, Department of Geography (U. Bristol, England, 1 st ed. 1996) trades grid cells until each region achieves the desired number of cells. The combinatorial approach of Herbert Edelsbrunner and Roman Waupotitsch, “A Combinatorial Approach to Cartograms,” Computational Geometry 343-360 (1997) computes a sequence of piecewise linear homeomorphisms of the mesh that preserve its topology. While the first method is good at preserving the shape of the polygons, the other two methods allow a very good fit for area but only poor shape preservation.
A synthesis of both approaches was recently described in Christopher J. Kocmoud and Donald H. House, “Continuous Cartogram Construction,” Proceedings IEEE Visualization 197-204 (1998) (FIG. 2H). A force-based model is proposed that alternately optimizes the shape and the area error. Although the results are better than most other methods, the complex optimization algorithm has a prohibitively high execution time. For example, 18 hours is required for a modest-sized map with 744 vertices.
The currently available solutions have two major problems: first, the high time complexity of the algorithms restricts their use to static applications with a small number of polygons and vertices. Second, they have very limited shape preservation. Although the recent work by Kocmoud and House provides nice results, some effectiveness problems remain. One problem is the significant deformation of the global shape. In evaluating the different heuristic solutions which have been proposed so far, the present inventors have found that the insufficient preservation of the global shape is one of the most important factors for cartograms to be effective, and it is certainly at least as important as the preservation of interior polygon shapes.
There is presently a need to make dynamic cartograms for on-line network monitoring, such as display of traffic or transaction event levels by country, state, and local regions. That application requires cartogram generation on the fly, and further requires generation of cartograms with maximum preservation of the global shape as well as preservation of the shapes of the interior polygons. To the inventors' knowledge, there is currently no currently available algorithm with adequate speed to perform that function.